%% copy riak-0.14.2 source to learn dynamo implementation and erlang
%% author: lichuang
%% copy source from riak_core_gossip.erl

%% @doc riak_core_gossip takes care of the mechanics of shuttling a from one
%% node to another upon request by other Riak processes.
%%
%% Additionally, it occasionally checks to make sure the current node has its
%% fair share of partitions, and also sends a copy of the ring to some other
%% random node, ensuring that all nodes eventually synchronize on the same
%% understanding of the Riak cluster. This interval is configurable, but
%% defaults to once per minute.

-module(edynamo_gossip).
-export([start_link/0, stop/0]).
-export([init/1, handle_call/3, handle_cast/2, handle_info/2,
         terminate/2, code_change/3]).
-export ([send_ring/1, send_ring/2, remove_from_cluster/1]).

%% ===================================================================
%% Public API
%% ===================================================================

%% send_ring/1 -
%% Send the current node's ring to some other node.
send_ring(ToNode) -> send_ring(node(), ToNode).

%% send_ring/2 -
%% Send the ring from one node to another node.
%% Does nothing if the two nodes are the same.
send_ring(Node, Node) ->
  ok;
send_ring(FromNode, ToNode) ->
  gen_server:cast({?MODULE, FromNode}, {send_ring_to, ToNode}).

start_link() ->
  gen_server:start_link({local, ?MODULE}, ?MODULE, [], []).

stop() ->
  gen_server:cast(?MODULE, stop).

%% ===================================================================
%% gen_server behaviour
%% ===================================================================
%% @private
init(_State) ->
  schedule_next_gossip(),
  {ok, true}.

%% @private
handle_call(_, _From, State) ->
  {reply, ok, State}.

%% @private
handle_cast({send_ring_to, Node}, RingChanged) ->
  {ok, MyRing} = edynamo_ring_manager:get_my_ring(),
  gen_server:cast({?MODULE, Node}, {reconcile_ring, MyRing}),
  {noreply, RingChanged};

handle_cast({reconcile_ring, OtherRing}, RingChanged) ->
  % Compare the two rings, see if there is anything that
  % must be done to make them equal...
  {ok, MyRing} = edynamo_ring_manager:get_my_ring(),
  case edynamo_ring:reconcile(OtherRing, MyRing) of
    {no_change, _} ->
      {noreply, RingChanged};
    {new_ring, ReconciledRing} ->
      % Rebalance the new ring and save it
      BalancedRing = claim_until_balanced(ReconciledRing),
      edynamo_ring_manager:set_my_ring(BalancedRing),
      % Finally, push it out to another node - expect at least two nodes now
      RandomNode = edynamo_ring:random_other_node(BalancedRing),
      send_ring(node(), RandomNode),
      {noreply, true}
  end;

handle_cast(_, State) ->
    {noreply, State}.

%% @private
handle_info(_Info, State) -> {noreply, State}.

%% @private
terminate(_Reason, _State) ->
    ok.

%% @private
code_change(_OldVsn, State, _Extra) ->
    {ok, State}.

%% ===================================================================
%% Internal functions
%% ===================================================================
schedule_next_gossip() ->
  MaxInterval = app_helper:get_env(edynamo, gossip_interval),
  Internal = random:uniform(MaxInterval),
  timer:apply_after(Internal, gen_server, cast, [?MODULE, gossip_ring]).

claim_until_balanced(Ring) ->
  {WMod, WFun} = app_helper:get_env(edynamo, wants_claim_fun),
  NeedsIndexes = apply(WMod, WFun, [Ring]),
  case NeedsIndexes of
    no ->
      Ring;
    {yes, _NumToClaim} ->
      {CMod, CFun} = app_helper:get_env(edynamo, choose_claim_fun),
      NewRing = CMod:CFun(Ring),
      claim_until_balanced(NewRing)
  end.

remove_from_cluster(ExitingNode) ->
  % Set the remote node to stop claiming.
  % Ignore return of rpc as this should succeed even if node is offline
  rpc:call(ExitingNode, application, set_env,
           [edynamo, wants_claim_fun, {edynamo_claim, never_wants_claim}]),
         
  % Get a list of indices owned by the ExitingNode...
  {ok, Ring} = edynamo_ring_manager:get_my_ring(),
  AllOwners  = edynamo_ring:all_owners(Ring),

  % Transfer indexes to other nodes...
  ExitRing =
    case attempt_simple_transfer(Ring, AllOwners, ExitingNode) of
      {ok, NR} ->
        NR;
      target_n_fail ->
        %% re-diagonalize
        %% first hand off all claims to *any* one else,
        %% just so rebalance doesn't include exiting node
        Members = edynamo_ring:all_members(Ring),
        Other   = hd(lists:delete(ExitingNode, Members)),
        TempRing = lists:foldl(
                    fun({I, N}, R) when N == ExitingNode ->
                        edynamo_ring:transfer_node(I, Other, R);
                      (_, R) -> R
                    end,
                    Ring,
                    AllOwners),
        edynamo_claim:claim_until_balanced(TempRing, Other)
  end,

  % Update our local copy of the ring
  edynamo_ring_manager:set_my_ring(ExitRing),

  % Send the new ring to all other rings
  [send_ring(X) || X <- edynamo_ring:all_members(Ring)].

attempt_simple_transfer(Ring, Owners, ExitingNode) ->
  TargetN = app_helper:get_env(edynamo, target_n_val),
  attempt_simple_transfer(Ring, Owners,
                          TargetN,
                          ExitingNode, 0,
                          [{O, -TargetN} || O <- edynamo_ring:all_members(Ring),
                                            O /= ExitingNode]).

attempt_simple_transfer(Ring, [{P, Exit} | Rest], TargetN, Exit, Idx, Last) ->
  %% handoff
  case [N || {N, I} <- Last, Idx - I >= TargetN] of
    [] ->
      target_n_fail;
    Candidates ->
      %% these nodes don't violate target_n in the reverse direction
      StepsToNext = fun(Node) ->
                      length(lists:takewhile(
                              fun({_, Owner}) -> Node /= Owner end,
                              Rest))
                    end,
      case lists:filter(fun(N) ->
                          Next = StepsToNext(N),
                          (Next + 1 >= TargetN)
                              orelse (Next == length(Rest))
                        end,
                        Candidates) of
        [] ->
          target_n_fail;
        Qualifiers ->
          %% these nodes don't violate target_n forward
          Chosen = lists:nth(random:uniform(length(Qualifiers)),
                             Qualifiers),
          %% choose one, and do the rest of the ring
          attempt_simple_transfer(
            edynamo_ring:transfer_node(P, Chosen, Ring),
            Rest, TargetN, Exit, Idx + 1,
            lists:keyreplace(Chosen, 1, Last, {Chosen, Idx}))
      end
  end;
attempt_simple_transfer(Ring, [{_, N}|Rest], TargetN, Exit, Idx, Last) ->
  %% just keep track of seeing this node
  attempt_simple_transfer(Ring, Rest, TargetN, Exit, Idx+1,
    lists:keyreplace(N, 1, Last, {N, Idx}));
attempt_simple_transfer(Ring, [], _, _, _, _) ->
  {ok, Ring}.
